package q1970_latestDayToCross;

import CommonClass.UF;

public class Solution {
    int row, col;
    int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    /*
    与q803打砖块相同的思路，首先创建一个对应的矩阵，先将所有cells中的位置全部置为1，代表已经被水淹没
    注意 cells中的坐标是从1开始的，所以都要减去1
    然后建立并查集，并查集中有两个特殊的位置代表 row * col 和 row * col + 1 分别代表矩阵的上侧和矩阵的下侧
    当这两个联通时，代表我们能够穿过矩阵，否则不能成功
    首先遍历第一行和最后一行将所有靠在上下侧的节点与对应一侧union
    然后遍历矩阵，将所有相连的0节点union
    然后开始时间回溯，从cells的最后一天开始，每一天恢复一个块为0，然后检查是否使得上下侧变为联通
     */
    public int latestDayToCross(int row, int col, int[][] cells) {
        this.row = row;
        this.col = col;
        UF uf = new UF(row * col + 2);
        int[][] matrix = new int[row][col];
        for (int[] cell : cells) {
            matrix[cell[0] - 1][cell[1] - 1] = 1;
        }
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[0][j] == 0) uf.union(j, row * col);
        }
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[row - 1][j] == 0) uf.union(getIndex(row - 1, j), row * col + 1);
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (i > 0 && matrix[i][j] == 0 && matrix[i - 1][j] == 0) uf.union(getIndex(i, j), getIndex(i - 1, j));
                if (j > 0 && matrix[i][j] == 0 && matrix[i][j - 1] == 0) uf.union(getIndex(i, j), getIndex(i, j - 1));
            }
        }
        if (uf.isConnected(row * col, row * col + 1)) return cells.length;
        for (int i = cells.length - 1; i >= 0; i--) {
            int x = cells[i][0] - 1, y = cells[i][1] - 1;
            if (x == 0) uf.union(getIndex(x, y), row * col);
            if (x == row - 1) uf.union(getIndex(x, y), row * col + 1);
            for (int[] dir : dirs) {
                int next_x = x + dir[0], next_y = y + dir[1];
                if (next_x >= 0 && next_y >= 0 && next_x < row && next_y < col && matrix[next_x][next_y] == 0) uf.union(getIndex(x, y), getIndex(next_x, next_y));
            }
            matrix[x][y] = 0;
            if (uf.isConnected(row * col, row * col + 1)) return i;
        }
        return 0;
    }

    private int getIndex(int i, int j) {
        return i * col + j;
    }
}
